home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Entertainment / MacMud / Mud 4.0 / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-16  |  32.5 KB  |  1,401 lines  |  [TEXT/MPS ]
  1. /* 
  2.  *
  3.  * regexp.c - regular expression matching
  4.  *
  5.  * DESCRIPTION
  6.  *
  7.  *    Underneath the reformatting and comment blocks which were added to 
  8.  *    make it consistent with the rest of the code, you will find a
  9.  *    modified version of Henry Specer's regular expression library.
  10.  *    Henry's functions were modified to provide the minimal regular
  11.  *    expression matching, as required by P1003.  Henry's code was
  12.  *    copyrighted, and copy of the copyright message and restrictions
  13.  *    are provided, verbatim, below:
  14.  *
  15.  *    Copyright (c) 1986 by University of Toronto.
  16.  *    Written by Henry Spencer.  Not derived from licensed software.
  17.  *
  18.  *    Permission is granted to anyone to use this software for any
  19.  *    purpose on any computer system, and to redistribute it freely,
  20.  *    subject to the following restrictions:
  21.  *
  22.  *    1. The author is not responsible for the consequences of use of
  23.  *         this software, no matter how awful, even if they arise
  24.  *       from defects in it.
  25.  *
  26.  *    2. The origin of this software must not be misrepresented, either
  27.  *       by explicit claim or by omission.
  28.  *
  29.  *    3. Altered versions must be plainly marked as such, and must not
  30.  *       be misrepresented as being the original software.
  31.  *
  32.  *
  33.  * This version modified by Ian Phillipps to return pointer to terminating
  34.  * NUL on substitution string. [ Temp mail address ex-igp@camcon.co.uk ]
  35.  *
  36.  *    Altered by amylaar to support excompatible option and the
  37.  *      operators \< and >\ . ( 7.Sep. 1991 )
  38.  *
  39.  * regsub altered by amylaar to take an additional parameter specifying
  40.  * maximum number of bytes that can be written to the memory region
  41.  * pointed to by dest
  42.  *
  43.  *     Beware that some of this code is subtly aware of the way operator
  44.  *     precedence is structured in regular expressions.  Serious changes in
  45.  *     regular-expression syntax might require a total rethink.
  46.  *
  47.  * AUTHORS
  48.  *
  49.  *     Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
  50.  *     Henry Spencer, University of Torronto (henry@utzoo.edu)
  51.  *
  52.  * Sponsored by The USENIX Association for public distribution. 
  53.  *
  54.  */
  55.  
  56. /* Headers */
  57.  
  58. #include <stdio.h>
  59. #include <string.h>
  60. #include <ctype.h>
  61. #include "regexp.h"
  62. #include "lint.h" /* for free() */
  63.  
  64. /*
  65.  * The "internal use only" fields in regexp.h are present to pass info from
  66.  * compile to execute that permits the execute phase to run lots faster on
  67.  * simple cases.  They are:
  68.  *
  69.  * regstart    char that must begin a match; '\0' if none obvious
  70.  * reganch    is the match anchored (at beginning-of-line only)?
  71.  * regmust    string (pointer into program) that match must include, or NULL
  72.  * regmlen    length of regmust string
  73.  *
  74.  * Regstart and reganch permit very fast decisions on suitable starting points
  75.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  76.  * of lines that cannot possibly match.  The regmust tests are costly enough
  77.  * that regcomp() supplies a regmust only if the r.e. contains something
  78.  * potentially expensive (at present, the only such thing detected is * or +
  79.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  80.  * supplied because the test in regexec() needs it and regcomp() is computing
  81.  * it anyway.
  82.  */
  83.  
  84. /*
  85.  * Structure for regexp "program".  This is essentially a linear encoding
  86.  * of a nondeterministic finite-state machine (aka syntax charts or
  87.  * "railroad normal form" in parsing technology).  Each node is an opcode
  88.  * plus a "nxt" pointer, possibly plus an operand.  "Nxt" pointers of
  89.  * all nodes except BRANCH implement concatenation; a "nxt" pointer with
  90.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  91.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  92.  * opposed to a collection of them) is never concatenated with anything
  93.  * because of operator precedence.)  The operand of some types of node is
  94.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  95.  * particular, the operand of a BRANCH node is the first node of the branch.
  96.  * (NB this is *not* a tree structure:  the tail of the branch connects
  97.  * to the thing following the set of BRANCHes.)  The opcodes are:
  98.  */
  99.  
  100. /* definition    number    opnd?    meaning */
  101. #define    END    0        /* no    End of program. */
  102. #define    BOL    1        /* no    Match "" at beginning of line. */
  103. #define    EOL    2        /* no    Match "" at end of line. */
  104. #define    ANY    3        /* no    Match any one character. */
  105. #define    ANYOF    4        /* str    Match any character in this string. */
  106. #define    ANYBUT    5        /* str    Match any character not in this
  107.                  * string. */
  108. #define    BRANCH    6        /* node    Match this alternative, or the
  109.                  * nxt... */
  110. #define    BACK    7        /* no    Match "", "nxt" ptr points backward. */
  111. #define    EXACTLY    8        /* str    Match this string. */
  112. #define    NOTHING    9        /* no    Match empty string. */
  113. #define    STAR    10        /* node    Match this (simple) thing 0 or more
  114.                  * times. */
  115. #define WORDSTART 11        /* node matching a start of a word          */
  116. #define WORDEND 12        /* node matching an end of a word           */
  117. #define    OPEN    20        /* no    Mark this point in input as start of
  118.                  * #n. */
  119.  /* OPEN+1 is number 1, etc. */
  120. #define    CLOSE    30        /* no    Analogous to OPEN. */
  121.  
  122. /*
  123.  * Opcode notes:
  124.  *
  125.  * BRANCH    The set of branches constituting a single choice are hooked
  126.  *        together with their "nxt" pointers, since precedence prevents
  127.  *        anything being concatenated to any individual branch.  The
  128.  *        "nxt" pointer of the last BRANCH in a choice points to the
  129.  *        thing following the whole choice.  This is also where the
  130.  *        final "nxt" pointer of each individual branch points; each
  131.  *        branch starts with the operand node of a BRANCH node.
  132.  *
  133.  * BACK        Normal "nxt" pointers all implicitly point forward; BACK
  134.  *        exists to make loop structures possible.
  135.  *
  136.  * STAR        complex '*', are implemented as circular BRANCH structures 
  137.  *        using BACK.  Simple cases (one character per match) are 
  138.  *        implemented with STAR for speed and to minimize recursive 
  139.  *        plunges.
  140.  *
  141.  * OPEN,CLOSE    ...are numbered at compile time.
  142.  */
  143.  
  144. /*
  145.  * A node is one char of opcode followed by two chars of "nxt" pointer.
  146.  * "Nxt" pointers are stored as two 8-bit pieces, high order first.  The
  147.  * value is a positive offset from the opcode of the node containing it.
  148.  * An operand, if any, simply follows the node.  (Note that much of the
  149.  * code generation knows about this implicit relationship.)
  150.  *
  151.  * Using two bytes for the "nxt" pointer is vast overkill for most things,
  152.  * but allows patterns to get big without disasters.
  153.  */
  154. #define    OP(p)    (*(p))
  155. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  156. #define    OPERAND(p)    ((p) + 3)
  157.  
  158. /*
  159.  * Utility definitions.
  160.  */
  161.  
  162. #define SPECIAL 0x100
  163. #define LBRAC    ('('|SPECIAL)
  164. #define RBRAC    (')'|SPECIAL)
  165. #define ASTERIX    ('*'|SPECIAL)
  166. #define OR_OP    ('|'|SPECIAL)
  167. #define DOLLAR    ('$'|SPECIAL)
  168. #define DOT    ('.'|SPECIAL)
  169. #define CARET    ('^'|SPECIAL)
  170. #define LSQBRAC ('['|SPECIAL)
  171. #define RSQBRAC (']'|SPECIAL)
  172. #define LSHBRAC ('<'|SPECIAL)
  173. #define RSHBRAC ('>'|SPECIAL)
  174. #define    FAIL(m)    { regerror(m); return(NULL); }
  175. #define    ISMULT(c)    ((c) == ASTERIX)
  176. #define    META    "^$.[()|*\\"
  177. #ifndef CHARBITS
  178. #define CHARBITS    0xff
  179. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  180. #else
  181. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  182. #endif
  183. #define ISWORDPART(c) ( isalnum(c) || (c) == '_' )
  184.  
  185. /*
  186.  * Flags to be passed up and down.
  187.  */
  188. #define    HASWIDTH    01    /* Known never to match null string. */
  189. #define    SIMPLE        02    /* Simple enough to be STAR operand. */
  190. #define    SPSTART        04    /* Starts with * */
  191. #define    WORST        0    /* Worst case. */
  192.  
  193. /*
  194.  * Global work variables for regcomp().
  195.  */
  196. static short   *regparse;    /* Input-scan pointer. */
  197. static int      regnpar;    /* () count. */
  198. static char     regdummy;
  199. static char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
  200. static long     regsize;    /* Code size. */
  201.  
  202. /*
  203.  * Forward declarations for regcomp()'s friends.
  204.  */
  205. #ifndef STATIC
  206. #define    STATIC    static
  207. #endif
  208. STATIC char    *reg();
  209. STATIC char    *regbranch();
  210. STATIC char    *regpiece();
  211. STATIC char    *regatom();
  212. STATIC char    *regnode();
  213. STATIC char    *regnext();
  214. STATIC void     regc();
  215. STATIC void     reginsert();
  216. STATIC void     regtail();
  217. STATIC void     regoptail();
  218. #ifdef STRCSPN
  219. STATIC int      strcspn();
  220. #endif
  221.  
  222. /*
  223.  - regcomp - compile a regular expression into internal code
  224.  *
  225.  * We can't allocate space until we know how big the compiled form will be,
  226.  * but we can't compile it (and thus know how big it is) until we've got a
  227.  * place to put the code.  So we cheat:  we compile it twice, once with code
  228.  * generation turned off and size counting turned on, and once "for real".
  229.  * This also means that we don't allocate space until we are sure that the
  230.  * thing really will compile successfully, and we never have to move the
  231.  * code and thus invalidate pointers into it.  (Note that it has to be in
  232.  * one piece because free() must be able to free it all.)
  233.  *
  234.  * Beware that the optimization-preparation code in here knows about some
  235.  * of the structure of the compiled regexp.
  236.  */
  237. regexp *regcomp(exp,excompat)
  238. char           *exp;
  239. int        excompat;    /* \( \) operators like in unix ex */
  240. {
  241.     register regexp *r;
  242.     register char  *scan;
  243.     register char  *longest;
  244.     register int    len;
  245.     int             flags;
  246.     short       *exp2,*dest,c;
  247.     extern char    *xalloc();
  248.  
  249.     if (exp == (char *)NULL)
  250.     FAIL("NULL argument");
  251.  
  252.     exp2=(short*)alloca( (strlen(exp)+1) * (sizeof(short[8])/sizeof(char[8])) );
  253.     for ( scan=exp,dest=exp2; c= *scan++; ) {
  254.     switch (c) {
  255.         case '(':
  256.         case ')':
  257.         *dest++ = excompat ? c : c | SPECIAL;
  258.         break;
  259.         case '.':
  260.         case '*':
  261.         case '|':
  262.         case '$':
  263.         case '^':
  264.         case '[':
  265.         case ']':
  266.         *dest++ =  c | SPECIAL;
  267.         break;
  268.         case '\\':
  269.         switch ( c = *scan++ ) {
  270.             case '(':
  271.             case ')':
  272.             *dest++ = excompat ? c | SPECIAL : c;
  273.             break;
  274.             case '<':
  275.             case '>':
  276.             *dest++ = c | SPECIAL;
  277.             break;
  278.             case '{':
  279.             case '}':
  280.             FAIL("sorry, unimplemented operator");
  281.             case 'b': *dest++ = '\b'; break;
  282.             case 't': *dest++ = '\t'; break;
  283.             case 'r': *dest++ = '\r'; break;
  284.             default:
  285.             *dest++ = c;
  286.         }
  287.         break;
  288.         default:
  289.         *dest++ = c;
  290.     }
  291.     }
  292.     *dest=0;
  293.     /* First pass: determine size, legality. */
  294.     regparse = exp2;
  295.     regnpar = 1;
  296.     regsize = 0L;
  297.     regcode = ®dummy;
  298.     regc(MAGIC);
  299.     if (reg(0, &flags) == (char *)NULL)
  300.     return ((regexp *)NULL);
  301.  
  302.     /* Small enough for pointer-storage convention? */
  303.     if (regsize >= 32767L)    /* Probably could be 65535L. */
  304.     FAIL("regexp too big");
  305.  
  306.     /* Allocate space. */
  307.     r = (regexp *) xalloc(sizeof(regexp) + (unsigned) regsize);
  308.     if (r == (regexp *) NULL)
  309.     FAIL("out of space");
  310.  
  311.     /* Second pass: emit code. */
  312.     regparse = exp2;
  313.     regnpar = 1;
  314.     regcode = r->program;
  315.     regc(MAGIC);
  316.     if (reg(0, &flags) == NULL)
  317.     return ((regexp *) NULL);
  318.  
  319.     /* Dig out information for optimizations. */
  320.     r->regstart = '\0';        /* Worst-case defaults. */
  321.     r->reganch = 0;
  322.     r->regmust = NULL;
  323.     r->regmlen = 0;
  324.     scan = r->program + 1;    /* First BRANCH. */
  325.     if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  326.     scan = OPERAND(scan);
  327.  
  328.     /* Starting-point info. */
  329.     if (OP(scan) == EXACTLY)
  330.         r->regstart = *OPERAND(scan);
  331.     else if (OP(scan) == BOL)
  332.         r->reganch++;
  333.  
  334.     /*
  335.      * If there's something expensive in the r.e., find the longest
  336.      * literal string that must appear and make it the regmust.  Resolve
  337.      * ties in favor of later strings, since the regstart check works
  338.      * with the beginning of the r.e. and avoiding duplication
  339.      * strengthens checking.  Not a strong reason, but sufficient in the
  340.      * absence of others. 
  341.      */
  342.     if (flags & SPSTART) {
  343.         longest = NULL;
  344.         len = 0;
  345.         for (; scan != NULL; scan = regnext(scan))
  346.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  347.             longest = OPERAND(scan);
  348.             len = strlen(OPERAND(scan));
  349.         }
  350.         r->regmust = longest;
  351.         r->regmlen = len;
  352.     }
  353.     }
  354.     return (r);
  355. }
  356.  
  357. /*
  358.  - reg - regular expression, i.e. main body or parenthesized thing
  359.  *
  360.  * Caller must absorb opening parenthesis.
  361.  *
  362.  * Combining parenthesis handling with the base level of regular expression
  363.  * is a trifle forced, but the need to tie the tails of the branches to what
  364.  * follows makes it hard to avoid.
  365.  */
  366. static char *reg(paren, flagp)
  367. int             paren;        /* Parenthesized? */
  368. int            *flagp;
  369. {
  370.     register char  *ret;
  371.     register char  *br;
  372.     register char  *ender;
  373.     register int    parno;
  374.     int             flags;
  375.  
  376.     *flagp = HASWIDTH;        /* Tentatively. */
  377.  
  378.     /* Make an OPEN node, if parenthesized. */
  379.     if (paren) {
  380.     if (regnpar >= NSUBEXP)
  381.         FAIL("too many ()");
  382.     parno = regnpar;
  383.     regnpar++;
  384.     ret = regnode(OPEN + parno);
  385.     } else
  386.     ret = (char *)NULL;
  387.  
  388.     /* Pick up the branches, linking them together. */
  389.     br = regbranch(&flags);
  390.     if (br == (char *)NULL)
  391.     return ((char *)NULL);
  392.     if (ret != (char *)NULL)
  393.     regtail(ret, br);    /* OPEN -> first. */
  394.     else
  395.     ret = br;
  396.     if (!(flags & HASWIDTH))
  397.     *flagp &= ~HASWIDTH;
  398.     *flagp |= flags & SPSTART;
  399.     while (*regparse == OR_OP) {
  400.     regparse++;
  401.     br = regbranch(&flags);
  402.     if (br == (char *)NULL)
  403.         return ((char *)NULL);
  404.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  405.     if (!(flags & HASWIDTH))
  406.         *flagp &= ~HASWIDTH;
  407.     *flagp |= flags & SPSTART;
  408.     }
  409.  
  410.     /* Make a closing node, and hook it on the end. */
  411.     ender = regnode((paren) ? CLOSE + parno : END);
  412.     regtail(ret, ender);
  413.  
  414.     /* Hook the tails of the branches to the closing node. */
  415.     for (br = ret; br != (char *)NULL; br = regnext(br))
  416.     regoptail(br, ender);
  417.  
  418.     /* Check for proper termination. */
  419.     if (paren && *regparse++ != RBRAC) {
  420.     FAIL("unmatched ()");
  421.     } else if (!paren && *regparse != '\0') {
  422.     if (*regparse == RBRAC) {
  423.         FAIL("unmatched ()");
  424.     } else
  425.         FAIL("junk on end");/* "Can't happen". */
  426.     /* NOTREACHED */
  427.     }
  428.     return (ret);
  429. }
  430.  
  431. /*
  432.  - regbranch - one alternative of an | operator
  433.  *
  434.  * Implements the concatenation operator.
  435.  */
  436. static char  *regbranch(flagp)
  437. int            *flagp;
  438. {
  439.     register char  *ret;
  440.     register char  *chain;
  441.     register char  *latest;
  442.     int             flags;
  443.  
  444.     *flagp = WORST;        /* Tentatively. */
  445.  
  446.     ret = regnode(BRANCH);
  447.     chain = (char *)NULL;
  448.     while (*regparse != '\0' && *regparse != OR_OP && *regparse != RBRAC) {
  449.     latest = regpiece(&flags);
  450.     if (latest == (char *)NULL)
  451.         return ((char *)NULL);
  452.     *flagp |= flags & HASWIDTH;
  453.     if (chain == (char *)NULL)    /* First piece. */
  454.         *flagp |= flags & SPSTART;
  455.     else
  456.         regtail(chain, latest);
  457.     chain = latest;
  458.     }
  459.     if (chain == (char *)NULL)        /* Loop ran zero times. */
  460.     regnode(NOTHING);
  461.  
  462.     return (ret);
  463. }
  464.  
  465. /*
  466.  - regpiece - something followed by possible [*]
  467.  *
  468.  * Note that the branching code sequence used for * is somewhat optimized:  
  469.  * they use the same NOTHING node as both the endmarker for their branch 
  470.  * list and the body of the last branch.  It might seem that this node could 
  471.  * be dispensed with entirely, but the endmarker role is not redundant.
  472.  */
  473. static char *regpiece(flagp)
  474. int            *flagp;
  475. {
  476.     register char  *ret;
  477.     register short  op;
  478.     /* register char  *nxt; */
  479.     int             flags;
  480.  
  481.     ret = regatom(&flags);
  482.     if (ret == (char *)NULL)
  483.     return ((char *)NULL);
  484.  
  485.     op = *regparse;
  486.     if (!ISMULT(op)) {
  487.     *flagp = flags;
  488.     return (ret);
  489.     }
  490.     if (!(flags & HASWIDTH))
  491.     FAIL("* operand could be empty");
  492.     *flagp = (WORST | SPSTART);
  493.  
  494.     if (op == ASTERIX && (flags & SIMPLE))
  495.     reginsert(STAR, ret);
  496.     else if (op == ASTERIX) {
  497.     /* Emit x* as (x&|), where & means "self". */
  498.     reginsert(BRANCH, ret);    /* Either x */
  499.     regoptail(ret, regnode(BACK));    /* and loop */
  500.     regoptail(ret, ret);    /* back */
  501.     regtail(ret, regnode(BRANCH));    /* or */
  502.     regtail(ret, regnode(NOTHING));    /* null. */
  503.     } 
  504.     regparse++;
  505.     if (ISMULT(*regparse))
  506.     FAIL("nested *");
  507.  
  508.     return (ret);
  509. }
  510.  
  511. /*
  512.  - regatom - the lowest level
  513.  *
  514.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  515.  * it can turn them into a single node, which is smaller to store and
  516.  * faster to run.
  517.  */
  518. static char *regatom(flagp)
  519. int            *flagp;
  520. {
  521.     register char  *ret;
  522.     int             flags;
  523.  
  524.     *flagp = WORST;        /* Tentatively. */
  525.  
  526.     switch (*regparse++) {
  527.     case CARET:
  528.     ret = regnode(BOL);
  529.     break;
  530.     case DOLLAR:
  531.     ret = regnode(EOL);
  532.     break;
  533.     case DOT:
  534.     ret = regnode(ANY);
  535.     *flagp |= HASWIDTH | SIMPLE;
  536.     break;
  537.     case LSHBRAC:
  538.     ret = regnode(WORDSTART);
  539.     break;
  540.     case RSHBRAC:
  541.     ret = regnode(WORDEND);
  542.     break;
  543.     case LSQBRAC:{
  544.         register int    class;
  545.         register int    classend;
  546.  
  547.         if (*regparse == CARET) {    /* Complement of range. */
  548.         ret = regnode(ANYBUT);
  549.         regparse++;
  550.         } else
  551.         ret = regnode(ANYOF);
  552.         if (*regparse == RSQBRAC || *regparse == '-')
  553.         regc(*regparse++);
  554.         while (*regparse != '\0' && *regparse != RSQBRAC) {
  555.         if (*regparse == '-') {
  556.             regparse++;
  557.             if (*regparse == RSQBRAC || *regparse == '\0')
  558.             regc('-');
  559.             else {
  560.             class = (CHARBITS & *(regparse - 2)) + 1;
  561.             classend = (CHARBITS & *(regparse));
  562.             if (class > classend + 1)
  563.                 FAIL("invalid [] range");
  564.             for (; class <= classend; class++)
  565.                 regc(class);
  566.             regparse++;
  567.             }
  568.         } else
  569.             regc(*regparse++);
  570.         }
  571.         regc('\0');
  572.         if (*regparse != RSQBRAC)
  573.         FAIL("unmatched []");
  574.         regparse++;
  575.         *flagp |= HASWIDTH | SIMPLE;
  576.     }
  577.     break;
  578.     case LBRAC:
  579.     ret = reg(1, &flags);
  580.     if (ret == (char *)NULL)
  581.         return ((char *)NULL);
  582.     *flagp |= flags & (HASWIDTH | SPSTART);
  583.     break;
  584.     case '\0':
  585.     case OR_OP:
  586.     case RBRAC:
  587.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  588.     break;
  589.     case ASTERIX:
  590.     FAIL("* follows nothing");
  591.     break;
  592.     default:{
  593.         register int    len;
  594.         register short  ender;
  595.  
  596.         regparse--;
  597.         for (len=0; regparse[len] &&
  598.             !(regparse[len]&SPECIAL) && regparse[len] != RSQBRAC; len++) ;
  599.         if (len <= 0)
  600.         {
  601.         FAIL("internal disaster");
  602.         }
  603.         ender = *(regparse + len);
  604.         if (len > 1 && ISMULT(ender))
  605.         len--;        /* Back off clear of * operand. */
  606.         *flagp |= HASWIDTH;
  607.         if (len == 1)
  608.         *flagp |= SIMPLE;
  609.         ret = regnode(EXACTLY);
  610.         while (len > 0) {
  611.         regc(*regparse++);
  612.         len--;
  613.         }
  614.         regc('\0');
  615.     }
  616.     break;
  617.     }
  618.  
  619.     return (ret);
  620. }
  621.  
  622. /*
  623.  - regnode - emit a node
  624.  */
  625. static char *regnode(op)
  626. char            op;
  627. {
  628.     register char  *ret;
  629.     register char  *ptr;
  630.  
  631.     ret = regcode;
  632.     if (ret == ®dummy) {
  633.     regsize += 3;
  634.     return (ret);
  635.     }
  636.     ptr = ret;
  637.     *ptr++ = op;
  638.     *ptr++ = '\0';        /* Null "nxt" pointer. */
  639.     *ptr++ = '\0';
  640.     regcode = ptr;
  641.  
  642.     return (ret);
  643. }
  644.  
  645. /*
  646.  - regc - emit (if appropriate) a byte of code
  647.  */
  648. static void regc(b)
  649. char            b;
  650. {
  651.     if (regcode != ®dummy)
  652.     *regcode++ = b;
  653.     else
  654.     regsize++;
  655. }
  656.  
  657. /*
  658.  - reginsert - insert an operator in front of already-emitted operand
  659.  *
  660.  * Means relocating the operand.
  661.  */
  662. static void reginsert(op, opnd)
  663. char            op;
  664. char           *opnd;
  665. {
  666.     register char  *src;
  667.     register char  *dst;
  668.     register char  *place;
  669.  
  670.     if (regcode == ®dummy) {
  671.     regsize += 3;
  672.     return;
  673.     }
  674.     src = regcode;
  675.     regcode += 3;
  676.     dst = regcode;
  677.     while (src > opnd)
  678.     *--dst = *--src;
  679.  
  680.     place = opnd;        /* Op node, where operand used to be. */
  681.     *place++ = op;
  682.     *place++ = '\0';
  683.     *place++ = '\0';
  684. }
  685.  
  686. /*
  687.  - regtail - set the next-pointer at the end of a node chain
  688.  */
  689. static void regtail(p, val)
  690. char           *p;
  691. char           *val;
  692. {
  693.     register char  *scan;
  694.     register char  *temp;
  695.     register int    offset;
  696.  
  697.     if (p == ®dummy)
  698.     return;
  699.  
  700.     /* Find last node. */
  701.     scan = p;
  702.     for (;;) {
  703.     temp = regnext(scan);
  704.     if (temp == (char *)NULL)
  705.         break;
  706.     scan = temp;
  707.     }
  708.  
  709.     if (OP(scan) == BACK)
  710.     offset = scan - val;
  711.     else
  712.     offset = val - scan;
  713.     *(scan + 1) = (offset >> 8) & 0377;
  714.     *(scan + 2) = offset & 0377;
  715. }
  716.  
  717. /*
  718.  - regoptail - regtail on operand of first argument; nop if operandless
  719.  */
  720. static void regoptail(p, val)
  721. char           *p;
  722. char           *val;
  723. {
  724.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  725.     if (p == (char *)NULL || p == ®dummy || OP(p) != BRANCH)
  726.     return;
  727.     regtail(OPERAND(p), val);
  728. }
  729.  
  730. /*
  731.  * regexec and friends
  732.  */
  733.  
  734. /*
  735.  * Global work variables for regexec().
  736.  */
  737. static char    *reginput;    /* String-input pointer. */
  738. static char    *regbol;        /* Beginning of input, for ^ check. */
  739. static char   **regstartp;    /* Pointer to startp array. */
  740. static char   **regendp;    /* Ditto for endp. */
  741.  
  742. /*
  743.  * Forwards.
  744.  */
  745. STATIC int      regtry();
  746. STATIC int      regmatch();
  747. STATIC int      regrepeat();
  748.  
  749. #ifdef DEBUG
  750. int             regnarrate = 0;
  751. void            regdump();
  752. STATIC char    *regprop();
  753. #endif
  754.  
  755. /*
  756.  - regexec - match a regexp against a string
  757.  */
  758. int regexec(prog, string)
  759. register regexp *prog;
  760. register char  *string;
  761. {
  762.     register char  *s;
  763.  
  764.     /* Be paranoid... */
  765.     if (prog == (regexp *)NULL || string == (char *)NULL) {
  766.     regerror("NULL parameter");
  767.     return (0);
  768.     }
  769.     /* Check validity of program. */
  770.     if (UCHARAT(prog->program) != MAGIC) {
  771.     regerror("corrupted program");
  772.     return (0);
  773.     }
  774.     /* If there is a "must appear" string, look for it. */
  775.     if (prog->regmust != (char *)NULL) {
  776.     s = string;
  777.     while ((s = strchr(s, prog->regmust[0])) != (char *)NULL) {
  778.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  779.         break;        /* Found it. */
  780.         s++;
  781.     }
  782.     if (s == (char *)NULL)        /* Not present. */
  783.         return (0);
  784.     }
  785.     /* Mark beginning of line for ^ . */
  786.     regbol = string;
  787.  
  788.     /* Simplest case:  anchored match need be tried only once. */
  789.     if (prog->reganch)
  790.     return (regtry(prog, string));
  791.  
  792.     /* Messy cases:  unanchored match. */
  793.     s = string;
  794.     if (prog->regstart != '\0')
  795.     /* We know what char it must start with. */
  796.     while ((s = strchr(s, prog->regstart)) != (char *)NULL) {
  797.         if (regtry(prog, s))
  798.         return (1);
  799.         s++;
  800.     }
  801.     else
  802.     /* We don't -- general case. */
  803.     do {
  804.         if (regtry(prog, s))
  805.         return (1);
  806.     } while (*s++ != '\0');
  807.  
  808.     /* Failure. */
  809.     return (0);
  810. }
  811.  
  812. /*
  813.  - regtry - try match at specific point
  814.  */
  815. #ifdef __STDC__
  816.  
  817. static int regtry(regexp *prog, char *string)
  818.  
  819. #else
  820.  
  821. static int regtry(prog, string)
  822. regexp         *prog;
  823. char           *string;
  824.  
  825. #endif
  826. {
  827.     register int    i;
  828.     register char **sp;
  829.     register char **ep;
  830.  
  831.     reginput = string;
  832.     regstartp = prog->startp;
  833.     regendp = prog->endp;
  834.  
  835.     sp = prog->startp;
  836.     ep = prog->endp;
  837.     for (i = NSUBEXP; i > 0; i--) {
  838.     *sp++ = (char *)NULL;
  839.     *ep++ = (char *)NULL;
  840.     }
  841.     if (regmatch(prog->program + 1)) {
  842.     prog->startp[0] = string;
  843.     prog->endp[0] = reginput;
  844.     return (1);
  845.     } else
  846.     return (0);
  847. }
  848.  
  849. /*
  850.  - regmatch - main matching routine
  851.  *
  852.  * Conceptually the strategy is simple:  check to see whether the current
  853.  * node matches, call self recursively to see whether the rest matches,
  854.  * and then act accordingly.  In practice we make some effort to avoid
  855.  * recursion, in particular by going through "ordinary" nodes (that don't
  856.  * need to know whether the rest of the match failed) by a loop instead of
  857.  * by recursion.
  858.  */
  859. #ifdef __STDC__
  860.  
  861. static int regmatch(char *prog)
  862.  
  863. #else
  864.  
  865. static int regmatch(prog)
  866. char           *prog;
  867.  
  868. #endif
  869. {
  870.     register char  *scan;    /* Current node. */
  871.     char           *nxt;    /* nxt node. */
  872.  
  873.     scan = prog;
  874. #ifdef DEBUG
  875.     if (scan != (char *)NULL && regnarrate)
  876.     fprintf(stderr, "%s(\n", regprop(scan));
  877. #endif
  878.     while (scan != (char *)NULL) {
  879. #ifdef DEBUG
  880.     if (regnarrate)
  881.         fprintf(stderr, "%s...\n", regprop(scan));
  882. #endif
  883.     nxt = regnext(scan);
  884.  
  885.     switch (OP(scan)) {
  886.     case BOL:
  887.         if (reginput != regbol)
  888.         return (0);
  889.         break;
  890.     case EOL:
  891.         if (*reginput != '\0')
  892.         return (0);
  893.         break;
  894.     case ANY:
  895.         if (*reginput == '\0')
  896.         return (0);
  897.         reginput++;
  898.         break;
  899.     case WORDSTART:
  900.         if (reginput == regbol)
  901.         break;
  902.         if (*reginput == '\0' ||
  903.            ISWORDPART( *(reginput-1) ) || !ISWORDPART( *reginput ) )
  904.         return (0);
  905.         break;
  906.     case WORDEND:
  907.         if (*reginput == '\0')
  908.         break;
  909.         if ( reginput == regbol ||
  910.            !ISWORDPART( *(reginput-1) ) || ISWORDPART( *reginput ) )
  911.         return (0);
  912.         break;
  913.     case EXACTLY:{
  914.         register int    len;
  915.         register char  *opnd;
  916.  
  917.         opnd = OPERAND(scan);
  918.         /* Inline the first character, for speed. */
  919.         if (*opnd != *reginput)
  920.             return (0);
  921.         len = strlen(opnd);
  922.         if (len > 1 && strncmp(opnd, reginput, len) != 0)
  923.             return (0);
  924.         reginput += len;
  925.         }
  926.         break;
  927.     case ANYOF:
  928.         if (*reginput == '\0' || 
  929.          strchr(OPERAND(scan), *reginput) == (char *)NULL)
  930.         return (0);
  931.         reginput++;
  932.         break;
  933.     case ANYBUT:
  934.         if (*reginput == '\0' || 
  935.          strchr(OPERAND(scan), *reginput) != (char *)NULL)
  936.         return (0);
  937.         reginput++;
  938.         break;
  939.     case NOTHING:
  940.         break;
  941.     case BACK:
  942.         break;
  943.     case OPEN + 1:
  944.     case OPEN + 2:
  945.     case OPEN + 3:
  946.     case OPEN + 4:
  947.     case OPEN + 5:
  948.     case OPEN + 6:
  949.     case OPEN + 7:
  950.     case OPEN + 8:
  951.     case OPEN + 9:{
  952.         register int    no;
  953.         register char  *save;
  954.  
  955.         no = OP(scan) - OPEN;
  956.         save = reginput;
  957.  
  958.         if (regmatch(nxt)) {
  959.             /*
  960.              * Don't set startp if some later invocation of the same
  961.              * parentheses already has. 
  962.              */
  963.             if (regstartp[no] == (char *)NULL)
  964.             regstartp[no] = save;
  965.             return (1);
  966.         } else
  967.             return (0);
  968.         }
  969.         break;
  970.     case CLOSE + 1:
  971.     case CLOSE + 2:
  972.     case CLOSE + 3:
  973.     case CLOSE + 4:
  974.     case CLOSE + 5:
  975.     case CLOSE + 6:
  976.     case CLOSE + 7:
  977.     case CLOSE + 8:
  978.     case CLOSE + 9:{
  979.         register int    no;
  980.         register char  *save;
  981.  
  982.         no = OP(scan) - CLOSE;
  983.         save = reginput;
  984.  
  985.         if (regmatch(nxt)) {
  986.             /*
  987.              * Don't set endp if some later invocation of the same
  988.              * parentheses already has. 
  989.              */
  990.             if (regendp[no] == (char *)NULL)
  991.             regendp[no] = save;
  992.             return (1);
  993.         } else
  994.             return (0);
  995.         }
  996.         break;
  997.     case BRANCH:{
  998.         register char  *save;
  999.  
  1000.         if (OP(nxt) != BRANCH)    /* No choice. */
  1001.             nxt = OPERAND(scan);    /* Avoid recursion. */
  1002.         else {
  1003.             do {
  1004.             save = reginput;
  1005.             if (regmatch(OPERAND(scan)))
  1006.                 return (1);
  1007.             reginput = save;
  1008.             scan = regnext(scan);
  1009.             } while (scan != (char *)NULL && OP(scan) == BRANCH);
  1010.             return (0);
  1011.             /* NOTREACHED */
  1012.         }
  1013.         }
  1014.         break;
  1015.     case STAR:{
  1016.         register char   nextch;
  1017.         register int    no;
  1018.         register char  *save;
  1019.         register int    minimum;
  1020.  
  1021.         /*
  1022.          * Lookahead to avoid useless match attempts when we know
  1023.          * what character comes next. 
  1024.          */
  1025.         nextch = '\0';
  1026.         if (OP(nxt) == EXACTLY)
  1027.             nextch = *OPERAND(nxt);
  1028.         minimum = (OP(scan) == STAR) ? 0 : 1;
  1029.         save = reginput;
  1030.         no = regrepeat(OPERAND(scan));
  1031.         while (no >= minimum) {
  1032.             /* If it could work, try it. */
  1033.             if (nextch == '\0' || *reginput == nextch)
  1034.             if (regmatch(nxt))
  1035.                 return (1);
  1036.             /* Couldn't or didn't -- back up. */
  1037.             no--;
  1038.             reginput = save + no;
  1039.         }
  1040.         return (0);
  1041.         }
  1042.         break;
  1043.     case END:
  1044.         return (1);        /* Success! */
  1045.         break;
  1046.     default:
  1047.         regerror("memory corruption");
  1048.         return (0);
  1049.         break;
  1050.     }
  1051.  
  1052.     scan = nxt;
  1053.     }
  1054.  
  1055.     /*
  1056.      * We get here only if there's trouble -- normally "case END" is the
  1057.      * terminating point. 
  1058.      */
  1059.     regerror("corrupted pointers");
  1060.     return (0);
  1061. }
  1062.  
  1063. /*
  1064.  - regrepeat - repeatedly match something simple, report how many
  1065.  */
  1066. #ifdef __STDC__
  1067.  
  1068. static int regrepeat(char *p)
  1069.  
  1070. #else
  1071.  
  1072. static int regrepeat(p)
  1073. char           *p;
  1074.  
  1075. #endif
  1076. {
  1077.     register int    count = 0;
  1078.     register char  *scan;
  1079.     register char  *opnd;
  1080.  
  1081.     scan = reginput;
  1082.     opnd = OPERAND(p);
  1083.     switch (OP(p)) {
  1084.     case ANY:
  1085.     count = strlen(scan);
  1086.     scan += count;
  1087.     break;
  1088.     case EXACTLY:
  1089.     while (*opnd == *scan) {
  1090.         count++;
  1091.         scan++;
  1092.     }
  1093.     break;
  1094.     case ANYOF:
  1095.     while (*scan != '\0' && strchr(opnd, *scan) != (char *)NULL) {
  1096.         count++;
  1097.         scan++;
  1098.     }
  1099.     break;
  1100.     case ANYBUT:
  1101.     while (*scan != '\0' && strchr(opnd, *scan) == (char *)NULL) {
  1102.         count++;
  1103.         scan++;
  1104.     }
  1105.     break;
  1106.     default:            /* Oh dear.  Called inappropriately. */
  1107.     regerror("internal foulup");
  1108.     count = 0;        /* Best compromise. */
  1109.     break;
  1110.     }
  1111.     reginput = scan;
  1112.  
  1113.     return (count);
  1114. }
  1115.  
  1116.  
  1117. /*
  1118.  - regnext - dig the "nxt" pointer out of a node
  1119.  */
  1120. #ifdef __STDC__
  1121.  
  1122. static char *regnext(register char *p)
  1123.  
  1124. #else
  1125.  
  1126. static char *regnext(p)
  1127. register char  *p;
  1128.  
  1129. #endif
  1130. {
  1131.     register int    offset;
  1132.  
  1133.     if (p == ®dummy)
  1134.     return ((char *)NULL);
  1135.  
  1136.     offset = NEXT(p);
  1137.     if (offset == 0)
  1138.     return ((char *)NULL);
  1139.  
  1140.     if (OP(p) == BACK)
  1141.     return (p - offset);
  1142.     else
  1143.     return (p + offset);
  1144. }
  1145.  
  1146. #ifdef DEBUG
  1147.  
  1148. STATIC char    *regprop();
  1149.  
  1150. /*
  1151.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1152.  */
  1153. #ifdef __STDC__
  1154.  
  1155. void regdump(regexp *r)
  1156.  
  1157. #else
  1158.  
  1159. void regdump(r)
  1160. regexp         *r;
  1161.  
  1162. #endif
  1163. {
  1164.     register char  *s;
  1165.     register char   op = EXACTLY;    /* Arbitrary non-END op. */
  1166.     register char  *nxt;
  1167.     extern char    *strchr();
  1168.  
  1169.  
  1170.     s = r->program + 1;
  1171.     while (op != END) {        /* While that wasn't END last time... */
  1172.     op = OP(s);
  1173.     printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1174.     nxt = regnext(s);
  1175.     if (nxt == (char *)NULL)    /* nxt ptr. */
  1176.         printf("(0)");
  1177.     else
  1178.         printf("(%d)", (s - r->program) + (nxt - s));
  1179.     s += 3;
  1180.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1181.         /* Literal string, where present. */
  1182.         while (*s != '\0') {
  1183.         putchar(*s);
  1184.         s++;
  1185.         }
  1186.         s++;
  1187.     }
  1188.     putchar('\n');
  1189.     }
  1190.  
  1191.     /* Header fields of interest. */
  1192.     if (r->regstart != '\0')
  1193.     printf("start `%c' ", r->regstart);
  1194.     if (r->reganch)
  1195.     printf("anchored ");
  1196.     if (r->regmust != (char *)NULL)
  1197.     printf("must have \"%s\"", r->regmust);
  1198.     printf("\n");
  1199. }
  1200.  
  1201. /*
  1202.  - regprop - printable representation of opcode
  1203.  */
  1204. #ifdef __STDC__
  1205.  
  1206. static char *regprop(char *op)
  1207.  
  1208. #else
  1209.  
  1210. static char *regprop(op)
  1211. char           *op;
  1212.  
  1213. #endif
  1214. {
  1215.     register char  *p;
  1216.     static char     buf[50];
  1217.  
  1218.     strcpy(buf, ":");
  1219.  
  1220.     switch (OP(op)) {
  1221.     case BOL:
  1222.     p = "BOL";
  1223.     break;
  1224.     case EOL:
  1225.     p = "EOL";
  1226.     break;
  1227.     case ANY:
  1228.     p = "ANY";
  1229.     break;
  1230.     case ANYOF:
  1231.     p = "ANYOF";
  1232.     break;
  1233.     case ANYBUT:
  1234.     p = "ANYBUT";
  1235.     break;
  1236.     case BRANCH:
  1237.     p = "BRANCH";
  1238.     break;
  1239.     case EXACTLY:
  1240.     p = "EXACTLY";
  1241.     break;
  1242.     case NOTHING:
  1243.     p = "NOTHING";
  1244.     break;
  1245.     case BACK:
  1246.     p = "BACK";
  1247.     break;
  1248.     case END:
  1249.     p = "END";
  1250.     break;
  1251.     case OPEN + 1:
  1252.     case OPEN + 2:
  1253.     case OPEN + 3:
  1254.     case OPEN + 4:
  1255.     case OPEN + 5:
  1256.     case OPEN + 6:
  1257.     case OPEN + 7:
  1258.     case OPEN + 8:
  1259.     case OPEN + 9:
  1260.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1261.     p = (char *)NULL;
  1262.     break;
  1263.     case CLOSE + 1:
  1264.     case CLOSE + 2:
  1265.     case CLOSE + 3:
  1266.     case CLOSE + 4:
  1267.     case CLOSE + 5:
  1268.     case CLOSE + 6:
  1269.     case CLOSE + 7:
  1270.     case CLOSE + 8:
  1271.     case CLOSE + 9:
  1272.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1273.     p = (char *)NULL;
  1274.     break;
  1275.     case STAR:
  1276.     p = "STAR";
  1277.     break;
  1278.     default:
  1279.     regerror("corrupted opcode");
  1280.     break;
  1281.     }
  1282.     if (p != (char *)NULL)
  1283.     strcat(buf, p);
  1284.     return (buf);
  1285. }
  1286. #endif
  1287.  
  1288. /*
  1289.  * The following is provided for those people who do not have strcspn() in
  1290.  * their C libraries.  They should get off their butts and do something
  1291.  * about it; at least one public-domain implementation of those (highly
  1292.  * useful) string routines has been published on Usenet.
  1293.  */
  1294. #ifdef STRCSPN
  1295. /*
  1296.  * strcspn - find length of initial segment of s1 consisting entirely
  1297.  * of characters not from s2
  1298.  */
  1299.  
  1300. #ifdef __STDC__
  1301.  
  1302. static int strcspn(char *s1, char *s2)
  1303.  
  1304. #else
  1305.  
  1306. static int strcspn(s1, s2)
  1307. char           *s1;
  1308. char           *s2;
  1309.  
  1310. #endif
  1311. {
  1312.     register char  *scan1;
  1313.     register char  *scan2;
  1314.     register int    count;
  1315.  
  1316.     count = 0;
  1317.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1318.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1319.         if (*scan1 == *scan2++)
  1320.         return (count);
  1321.     count++;
  1322.     }
  1323.     return (count);
  1324. }
  1325. #endif
  1326.  
  1327.  
  1328. /*
  1329.  - regsub - perform substitutions after a regexp match
  1330.  */
  1331. #ifdef __STDC__
  1332.  
  1333. char *regsub(regexp *prog, char *source, char *dest, int n)
  1334.  
  1335. #else
  1336.  
  1337. char *regsub(prog, source, dest, n)
  1338. regexp         *prog;
  1339. char           *source;
  1340. char           *dest;
  1341. int        n;
  1342.  
  1343. #endif
  1344. {
  1345.     register char  *src;
  1346.     register char  *dst;
  1347.     register char   c;
  1348.     register int    no;
  1349.     register int    len;
  1350.     extern char    *strncpy();
  1351.  
  1352.     if (prog == (regexp *)NULL || 
  1353.     source == (char *)NULL || dest == (char *)NULL) {
  1354.     regerror("NULL parm to regsub");
  1355.     return NULL;
  1356.     }
  1357.     if (UCHARAT(prog->program) != MAGIC) {
  1358.     regerror("damaged regexp fed to regsub");
  1359.     return NULL;
  1360.     }
  1361.     src = source;
  1362.     dst = dest;
  1363.     while ((c = *src++) != '\0') {
  1364.     if (c == '&')
  1365.         no = 0;
  1366.     else if (c == '\\' && '0' <= *src && *src <= '9')
  1367.         no = *src++ - '0';
  1368.     else
  1369.         no = -1;
  1370.  
  1371.     if (no < 0) {        /* Ordinary character. */
  1372.         if (c == '\\' && (*src == '\\' || *src == '&'))
  1373.         c = *src++;
  1374.         if (--n < 0) {                /* amylaar */
  1375.         regerror("line too long");
  1376.         return NULL;
  1377.         }
  1378.         *dst++ = c;
  1379.     } else if (prog->startp[no] != (char *)NULL && 
  1380.            prog->endp[no] != (char *)NULL) {
  1381.         len = prog->endp[no] - prog->startp[no];
  1382.         if ( (n-=len) < 0 ) {        /* amylaar */
  1383.         regerror("line too long");
  1384.         return NULL;
  1385.         }
  1386.         strncpy(dst, prog->startp[no], len);
  1387.         dst += len;
  1388.         if (len != 0 && *(dst - 1) == '\0') {    /* strncpy hit NUL. */
  1389.         regerror("damaged match string");
  1390.         return NULL;
  1391.         }
  1392.     }
  1393.     }
  1394.     if (--n < 0) {            /* amylaar */
  1395.         regerror("line too long");
  1396.         return NULL;
  1397.     }
  1398.     *dst = '\0';
  1399.     return dst;
  1400. }
  1401.